Connectivity keeping stars or double-stars in 2-connected graphs

In Mader (2010), Mader conjectured that for every positive integer $k$ and every finite tree $T$ with order $m$, every $k$-connected, finite graph $G$ with $\delta \left(G\right)\ge ?\frac{3}{2}k?+m?1$ contains a subtree $T^{\prime }$ isomorphic to $T$ such that $G?V\left(T^{\prime }\right)$ is $k$-connected. In the same paper, Mader proved that the conjecture is true when $T$ is a path. Diwan and Tholiya (2009) verified the conjecture when $k=1$. In this paper, we will prove that Mader’s conjecture is true when $T$ is a star or double-star and $k=2$.     

A property on reinforcing edge-disjoint spanning hypertrees in uniform hypergraphs

Suppose that $H$ is a simple uniform hypergraph satisfying $\left|E\left(H\right)\right|=k(\left|V\left(H\right)\right|?1)$. A $k$-partition $\pi =(X_1,X_2,\dots ,X_k)$ of $E\left(H\right)$ such that $\left|X_i\right|=\left|V\left(H\right)\right|?1$ for $1\le i\le k$ is a uniform $k$-partition. Let $P_k\left(H\right)$ be the collection of all uniform $k$-partitions of $E\left(H\right)$ and define $\epsilon \left(\pi \right)={\sum }_{i=1}^{k}c\left(H\left(X_i\right)\right)?k$, where $c\left(H\right)$ denotes the number of maximal partition-connected sub-hypergraphs of $H$. Let $\epsilon \left(H\right)={min}_{\pi \in P_k\left(H\right)}\epsilon \left(\pi \right)$. Then $\epsilon \left(H\right)\ge 0$ with equality holds if and only if $H$ is a union of $k$ edge-disjoint spanning hypertrees. The parameter $\epsilon \left(H\right)$ is used to measure how close $H$ is being from a union of $k$ edge-disjoint spanning hypertrees.We prove that if $H$ is a simple uniform hypergraph with $\left|E\left(H\right)\right|=k(\left|V\left(H\right)\right|?1)$ and $\epsilon \left(H\right)>0$, then there exist $e\in E\left(H\right)$ and $e^{\prime }\in E\left(H^c\right)$ such that $\epsilon (H?e+e^{\prime })<\epsilon \left(H\right)$. This generalizes a former result, which settles a conjecture of Payan. The result iteratively defines a finite $\epsilon$-decreasing sequence of uniform hypergraphs $H_0,H_1,H_2,\dots ,H_m$ such that $H_0=H$, $H_m$ is the union of $k$ edge-disjoint spanning hypertrees, and such that two consecutive hypergraphs in the sequence differ by exactly one hyperedge.     

On the Semi-geostrophic System in Physical Space with General Initial Data

Archive for Rational Mechanics and Analysis - In order to accommodate general initial data, an appropriately relaxed notion of renormalized Lagrangian solutions for the Semi-Geostrophic system in...     

Flows in 3-edge-connected bidirected graphs

It was conjectured by A. Bouchet that every bidirected graph which admits a nowhere-zero k-flow admits a nowhere-zero 6-flow. He proved that the conjecture is true when 6 is replaced by 216. O. Zyka improved the result with 6 replaced by 30. R. Xu and C. Q. Zhang showed that the conjecture is true for 6-edge-connected graph, which is further improved by A. Raspaud and X. Zhu for 4-edge-connected graphs. The main result of this paper improves Zyka’s theorem by showing the existence of a nowhere-zero 25-flow for all 3-edge-connected graphs.     

Upper Bounds on List Star Chromatic Index of Sparse Graphs

A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'_st(G)of a graph G is the smallest integer k such that G has a star k-edge-coloring.The list star chromatic index ch'st(G)is defined analogously.The star edge coloring problem is known to be NP-complete,and it is even hard to obtain tight upper bound as it is unknown whether the star chromatic index for complete graph is linear or super linear.In this paper,we study,in contrast,the best linear upper bound for sparse graph classes.We show that for everyε>0 there exists a constant c(ε)such that if mad(G)<8/3-ε,then■and the coefficient 3/2 ofΔis the best possible.The proof applies a newly developed coloring extension method by assigning color sets with different sizes.     

Group Connectivity of 3-Edge-Connected Chordal Graphs

Let A be a finite abelian group and G be a digraph. The boundary of a function f: E(G)ZA is a function ‘f: V(G)ZA given by ‘f(v)=~_{e leaving v}f(e)m~_{e entering v}f(e). The graph G is A-connected if for every b: V(G)ZA with ~_{v] V(G)} b(v)=0, there is a function f: E(G)ZA{0} such that ‘f=b. In [J. Combinatorial Theory, Ser. B 56 (1992) 165-182], Jaeger et al showed that every 3-edge-connected graph is A-connected, for every abelian group A with |A|̈́. It is conjectured that every 3-edge-connected graph is A-connected, for every abelian group A with |A|̓ and that every 5-edge-connected graph is A-connected, for every abelian group A with |A|́.¶ In this note, we investigate the group connectivity of 3-edge-connected chordal graphs and characterize 3-edge-connected chordal graphs that are A-connected for every finite abelian group A with |A|́.     

Connectivity threshold and recovery time in rank-based models for complex networks

We study a generalized version of the protean graph (a probabilistic model of the World Wide Web) with a power law degree distribution, in which the degree of a vertex depends on its age as well as its rank. The main aim of this paper is to study the behaviour of the protean process near the connectivity threshold. Since even above the connectivity threshold it is still possible that the graph becomes disconnected, it is important to investigate the recovery time for connectivity, that is, how long we have to wait to regain the connectivity.